package Ep02_LinkedList._0206;

import Ep02_LinkedList.ListNode;

import java.util.Stack;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/3/8 10:43
 * 说明：力扣 0206 翻转链表  --->  栈，后入先出，正好可以用于翻转链表
 */

public class ReverseStack {
    public ListNode reverseList(ListNode head){
        if (head == null ){
            return null;
        }
        if (head.next == null){
            return head;
        }

        Stack<ListNode> stack = new Stack<>();
        ListNode cur = head;
        // 使用一个遍历变量cur指针将链表中的每个节点都压入栈中
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        // 创建一个虚拟头结点
        ListNode dummyHead = new ListNode(-1);
        cur = dummyHead;
        while (!stack.isEmpty()){
            cur.next = stack.pop();
            cur = cur.next;
        }

        // 最后一个节点 1 的next还是节点 2，因此要将 1 的next指向null
        cur.next = null;

        return dummyHead.next;
    }
}
